package Algorithm.array;

/**
 * @Desc:   接雨水
 * @author: cww
 * @DateTime: 2020-04-04 17:16
 */

public class rain {

    public static void main(String[] args) {
        int[] i  = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap3(i));
    }
    public static int trap(int[] height) {
        int sum =0;
        if(height.length <= 1) return sum;
        for(int i=0;i<height.length;i++){
            if(height[i] == 0) continue;
            if(i<height.length-1 && (height[i]==height[i+1] || height[i+1]>height[i])) continue;
            int iner = 0, temp = 0, temp2= -1;
            for(int j =i+1;j<height.length;j++){
                if(height[j]<height[i]) {
                    temp += height[j];
                    if(j == height.length - 1 && temp2 >= 0&&height[j] <= height[temp2]) {
                        i = j-1;
                        break;
                    }
                    if(j-i-1==0) continue;
                    if(temp2 >= 0 && height[j] <= height[temp2]) continue;
                    int hei = Math.min(height[j],height[i]);
                    int temp1 = hei * (j-i-1) - temp + height[j];
                    if(temp1 <= 0) continue;
                    temp2 = j;
                    iner = Math.max(temp1, iner);
                    continue;
                }
                iner = height[i] * (j-i-1) - temp;
                i = j-1;
                break;
            }
            sum += iner;
        }
        return sum;
    }

    public static int trap1(int[] height) {
        int sum = 0;
        //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
        for (int i = 1; i < height.length - 1; i++) {
            int max_left = 0;
            //找出左边最高
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] > max_left) {
                    max_left = height[j];
                }
            }
            int max_right = 0;
            //找出右边最高
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] > max_right) {
                    max_right = height[j];
                }
            }
            //找出两端较小的
            int min = Math.min(max_left, max_right);
            //只有较小的一段大于当前列的高度才会有水，其他情况不会有水
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

    public static int trap2(int[] height) {
        int sum = 0;
        int max_left = 0;
        int[] max_right = new int[height.length];
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            max_left = Math.max(max_left, height[i - 1]);
            int min = Math.min(max_left, max_right[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

    public static int trap3(int[] height){
        if(height == null||height.length <3) return 0;
        int sum = 0;
        int leftMax = 0, rightMax = 0;
        int left = 0, right = height.length-1;
        while(left<right) {
            leftMax = Math.max(leftMax,height[left]);
            rightMax = Math.max(rightMax,height[right]);
            if(leftMax<=rightMax){
                sum += leftMax - height[left];
                left++;
            }else{
                sum += rightMax - height[right];
                right--;
            }
        }
        return sum;
    }
}
